#include"DynamicArray.h"
#include<stdio.h>
#include<stdlib.h>




struct DynamicArray
{
    ElementType *a; //数组指针
    int capacity;   //数组容量
    int size;       //元素个数
};



DArray *InitDArray( int capacity )  //初始化
{
    DArray *array = (DArray*)malloc(sizeof(DArray)); //在堆上申请一块内存，用来放结构体 array
    if(array == NULL)   
    {
        printf("InitDArray malloc 申请失败\n");   //如果申请失败了，返回空指针就行
        return NULL;
    }
    //如果第一块内存申请成功，把结构体里的元素赋值

    array->size = 0;    //数组里一开始的元素个数一定是 0 ，还没放东西进去
    
    array->capacity = capacity;     //数组的容量是我们自己定的，所以把传进来的值赋值就行
    
    array->a = (ElementType*)malloc(sizeof(ElementType) * capacity );   //再次申请一片内存放  
                                                                     //ElementType类型的指针
    
    if(array->a == NULL)
    {
        printf("InitDArray malloc a 申请失败\n");
        free(array); //如果申请失败，直接把结构体 释放
        return NULL; 
    }
    return array;
}





void InsertTail(DArray*array,ElementType element)
{
    if(array->size >= array->capacity)//数组满了的情况
    {
        array->capacity *= 2;
        
        ElementType*newPtr = realloc(array->a,sizeof(ElementType) * array->capacity);
        
        if(newPtr == NULL)
        {
            printf("扩容数组失败!不能进行插入\n");
            array->capacity/=2;
            return;
        }
        array->a = newPtr;
    }
    array->a[array->size++] = element;//在结构体array的数组a的
}


void PrintDArray(DArray *array,void (*print)(ElementType))
{   
    
    printf("size :%d   capacity:%d\n",array->size,array->capacity);
    for(int i = 0;i < array->size;i++)
    {
        print(array->a[i]);

    }
    printf("\n");
}



ElementType *FindByElement(DArray *array, ElementType element)     //
{
    for(int i = 0;i < array->size;i++)
    {
        if(array->a[i] == element)
            return &array->a[i];
    }
    return NULL;
}



void RemoveByIndex(DArray *array, int index)
{   
    if(index<0 || index > array->size)
    {
        printf("非法位置");
        return;
    }

    for(int i = index; i < array->size;i++)
    {
        array->a[i] = array->a[i+1];
    }
    array->size--;
}



void RemoveByElement(DArray *array, ElementType element)
{
    for(int i=0;i<array->size;i++)
    if(array->a[i] == element)
    {
        RemoveByIndex(array,i);
        i--;
    }
}



void FastSort(ElementType *a,int start,int end,bool (*Compare)(ElementType,ElementType))
{
    if(start >= end)
        return;
    
    int left = start;
    int right = end;
    
    ElementType temp = a[left];//将最左边的值定为基准值
   
    while(left < right)
    {
        //右边往左动，找比基准值小的数
        while(Compare( a[right] , temp) && left < right)
            right--;
        
        if(left < right)
        {
            a[left++] = a[right];//把右边的比基准值小的数扔到左边的指针
        }
        
        //左边往右边动，找比基准值大的数
        while(Compare(temp,a[left]) && left < right)
            left++;
        if(left < right)
        {
            a[right--] = a[left];//把左边比基准值大的数扔到右边
        }
    }
    a[left] = temp;

    //递归
    FastSort(a,start,left - 1,Compare);
    FastSort(a,right+1,end,Compare);

}


void Sort(DArray *a, bool (*Compare)(ElementType,ElementType))
{
    FastSort(a->a,0,a->size-1,Compare);
}





void FreeDArray(DArray *array, void (*Free)(ElementType))
{   
    for(int i=0;i<array->size;i++)
    {
        Free(array->a[i]);
    }
    
    free(array->a);
    free(array);
}


